/*
 * add.cpp
 *
 *  Created on: May 23, 2011
 *      Author: Manslaughter
 */

#include "BigInt.h"
#include <stdio.h>
using namespace APIAL;

/*
	Performs result = left+right.
	Assumes scratchSpace is not an alias of any argument.
*/
void APIAL::Add(BigInt *left, BigInt *right, BigInt *result, BigInt *scratchSpace) {
    // Check for subtraction
    if (left->positive && !right->positive) {
		right->positive = true;
        Subtract(left, right, result, scratchSpace);
		right->positive = false;
        return;
    } else if (!(left->positive) && right->positive) {
		left->positive = true;
        Subtract(right, left, result, scratchSpace);
		left->positive = false;
        return;
    }

	// Watch out for aliases
	bool resultAlias = (left == result) || (right == result);

	// Add right first, if alias
	if (right == result) {
		BigInt *swap = left;
		left = right;
		right = swap;
	}

	// Determine maximum size (addition adds at most one chunk)
	int maxSize = left->size;
	if (right->size > maxSize) {
		maxSize = right->size;
	} 

	// Reallocate result if necessary
	if (result->capacity <= maxSize) {
		result->resize(maxSize+1, resultAlias);
	}

	// Reallocate scratch space if necessary
	bool notNormalized = !left->normalized || !right->normalized;
	if (scratchSpace->capacity <= maxSize && (notNormalized || resultAlias)) {
		scratchSpace->resize(maxSize+1, false);
	}

	// Aliasing is special
	if (resultAlias) {
		// Left is the alias because of earlier swap
		if (notNormalized) {
			// Result ends up in result (an alias)
			BigInt::addNoCheck(left, right, scratchSpace, result, 0, maxSize);
		} else {
			// Result ends in scratchSpace, must swap
			BigInt::addNoCheck(left, right, scratchSpace, scratchSpace, 0, maxSize);
			result->normalized = scratchSpace->normalized;
			result->size = scratchSpace->size;
			BigInt::chunkType *swap = result->chunks;
			result->chunks = scratchSpace->chunks;
			scratchSpace->chunks = swap;
		}
	} else {
		BigInt::addNoCheck(left, right, scratchSpace, result, 0, maxSize);
	}

	// Done
    return;
}

/*
  Adds two BigInts.  
  1) If the operands are not normalized:
		scratchSpace = left+right+leftCarry;
		result = scratchSpace+scratchSpaceCarry+rightCarry;
  2) If the operands are normalized:
		result = left+right
  Assumes no improper aliasing, no subtraction, and proper allocation.
*/
void BigInt::addNoCheck(BigInt *left, BigInt *right, BigInt *scratchSpace, BigInt *result, int start, int end) {
	// Get minimum size
	int minSize = left->size;
	BigInt *longerOperand = right;
	if (right->size < minSize) {
		minSize = right->size;
		longerOperand = left;
	}
	if (end < minSize) {
		minSize = end;
	}

	// Clear the last chunk at minSize
	result->chunks[minSize] = 0;

	// Add up to minSize
	if (start >= minSize) {
		result->size = minSize-1;
	} else {
		if (left->normalized && right->normalized) {
			// Both are normalized, only one reduction necessary
			addReductionNAndN(left, right, result, start, minSize);
		} else {
			// At least one is not normalized, two reductions necessary
			addReductionNcAndN(left, right, scratchSpace, start, minSize);
			addReductionNcAndC(scratchSpace, right, result, start, minSize);
		}
	}

	// Add from minSize to maxSize
	if (minSize < end) {
		addReductionNc(longerOperand, result->chunks[minSize], result, minSize, end);
	}

	// Result is the same sign
	result->positive = left->positive;

	// Done
	return;
}

/*
	Add result = op1[nonCarryBits]+op2[nonCarryBits]
*/
void BigInt::addReductionNAndN(BigInt *op1, BigInt *op2, BigInt* result, int start, int end) {
	// First chunk
	if (start <= 0) {
		result->chunks[0] = (op1->chunks[0]&op1->nonCarryBitsMask)+
			(op2->chunks[0]&op2->nonCarryBitsMask);
		start = 1;
	}

	// Middle chunks
	#pragma omp parallel for 
	for (int i = start; i < end; i++) {
		result->chunks[i] = (op1->chunks[i]&op1->nonCarryBitsMask)+
			(op2->chunks[i]&op2->nonCarryBitsMask);
	}

	// Final size
	result->size = end;

	// Final chunk
	result->chunks[end] += op1->chunks[end-1]>>op1->nonCarryBits;
	if (result->chunks[end] == 0) {
		result->size = end;
	} else {
		result->size = end-1;
	}

	// Result is not normalized
	result->normalized = false;
}

/*
	Add result = op1[nonCarryBits]+op1[carryBits]+op2[nonCarryBits]
*/
void BigInt::addReductionNcAndN(BigInt *op1, BigInt *op2, BigInt* result, int start, int end) {
	// First chunk
	if (start <= 0) {
		result->chunks[0] = (op1->chunks[0]&op1->nonCarryBitsMask)+
			(op2->chunks[0]&op2->nonCarryBitsMask);
		start = 1;
	}

	// Middle chunks
	#pragma omp parallel for 
	for (int i = start; i < end; i++) {
		result->chunks[i] = (op1->chunks[i]&op1->nonCarryBitsMask)+
			(op2->chunks[i]&op2->nonCarryBitsMask)+
			(op1->chunks[i-1]>>op1->nonCarryBits);
	}

	// Add the last carry bit
	result->chunks[end] += op1->chunks[end-1]>>op1->nonCarryBits;
	if (result->chunks[end] == 0) {
		result->size = end;
	} else {
		result->size = end+1;
	}

	// Result is not normalized
	result->normalized = false;
}

/*
	Add result = op1[nonCarryBits]+op1[carryBits]+op2[carryBits]
*/
void BigInt::addReductionNcAndC(BigInt *op1, BigInt *op2, BigInt* result, int start, int end) {
	// First chunk
	if (start <= 0) {
		result->chunks[0] = (op1->chunks[0]&op1->nonCarryBitsMask);
		start = 1;
	}

	// Middle chunks
	#pragma omp parallel for 
	for (int i = start; i < end; i++) {
		result->chunks[i] = (op1->chunks[i]&op1->nonCarryBitsMask)+
			(op2->chunks[i-1]>>op2->nonCarryBits)+
			(op1->chunks[i-1]>>op1->nonCarryBits);
	}

	// Add the last carry bit
	result->chunks[end] += (op1->chunks[end-1]>>op1->nonCarryBits)+
		(op2->chunks[end-1]>>op2->nonCarryBits);
	if (result->chunks[end] == 0) {
		result->size = end;
	} else {
		result->size = end+1;
	}

	// Result is not normalized
	result->normalized = false;
}

/*
	Add result = op1[nonCarryBits]+op1[carryBits]
*/
void BigInt::addReductionNc(BigInt *op1, chunkType carryIn, BigInt *result, int start, int end) {
	// First chunk
	result->chunks[start] = (op1->chunks[start]&op1->nonCarryBitsMask)+
		carryIn;
	start++;

	// Middle chunks
	#pragma omp parallel for
	for (int i = start; i < end; i++) {
		result->chunks[i] = (op1->chunks[i]&op1->nonCarryBitsMask)+
			(op1->chunks[i-1]>>op1->nonCarryBits);
	}

	// Final chunk
	result->chunks[end] += op1->chunks[end-1]>>op1->nonCarryBits;
	if (result->chunks[end] == 0) {
		result->size = end;
	} else {
		result->size = end+1;
	}

	// Result is not normalized
	result->normalized = false;
}

void BigInt::normalize(BigInt &left) {
    // Check if already normalized
    if (left.normalized)
        return;

    // Check if we need to resize the array
    if (left.size >= left.capacity) {
        left.resize(left.size+1, true);
    }

    // Normalize (serial)
    chunkType carryIn = 0;
    chunkType carryOut;
    for (int i = 0; i < (int)left.size; i++) {
        // Save the previous carry out bits
        carryOut = left.chunks[i] >> left.nonCarryBits;

        // Get the new chunk result
        left.chunks[i] = (left.chunks[i]&left.nonCarryBitsMask)+carryIn;

        // Add any new carry bits to the next carry in
        carryIn = carryOut+(left.chunks[i] >> left.nonCarryBits);

        // Mask the carry out
        left.chunks[i] = left.chunks[i]&left.nonCarryBitsMask;
    }

	// Set final chunk
	left.chunks[left.size] = carryIn;
	if (carryIn != 0) {
		left.size++;
	}

	// Finished
	left.normalized = true;
}

